Digital networks have been developed to facilitate the transfer of information including data and programs among digital computer systems and numerous other types of devices. A variety of types of networks have been developed and implemented using diverse information transfer methodologies. In modern networks, information is transferred through a mesh of switching nodes which are interconnected by communication links in a variety of patterns. The mesh interconnection pattern can allow for a number of paths to be available through the network from each computer system or other device to another computer system or other device.
Information transferred from a source device to a destination device is generally transferred in the form of fixed or variable-length data packets, each of which is in general received by a switching node over a communication link and transmitted over another communication link to facilitate transfer of the packet to the destination device or to another switching node along a path to the destination device. Each packet typically includes address information including a source address that identifies the device that generated the packet and a destination address that identifies the particular device or devices which are to receive the packet. Transfer of data packets on the network typically takes place in accordance with a packet transfer protocol. In common networks such as the Internet, a protocol used is the common Internet Protocol (IP).
Typically, a switching node includes one or more input ports, each of which is coupled to a communication link on the network to receive data packets, and one or more output ports, each of which is coupled to a communication link on the network to transmit packets. Each node typically also includes a switching fabric that couples data packets from the input ports to the output ports for transmission.
A typical switching node also includes one or more packet queues at the input and/or output side of the node for temporarily storing packets that are to be transferred onto the network. Input-queued switches have the queues at the input ports, and output-queued switches have the queues at the input ports. In either case, each link to which an output port is coupled can be associated with multiple queues.
The configuration of the queuing structure is determined by the queuing approach implemented in the node. For example, under a priority queuing approach, the queues associated with a particular output can be defined according to a predetermined packet transfer priority scheme. One queue may be assigned to store only the highest priority packets. Another queue may store only the next highest level priority packets, and so on. When a packet is to be transferred onto the associated network link, if a packet is stored in the highest priority queue, then that packet is transferred. If no packet is present in that queue, then the next queue is checked, and so on. This approach ensures that the highest priority packets will always be transferred first.
In a weighted queuing approach, such as Weighted Fair Queuing (WFQ), each queue is given a predetermined weight value. Packets are then transferred out of the queues according to their weights. For example, in a system with four queues for an output port, a weighting scheme can be used in which the four queues are assigned weight values of 8, 4, 2, and 2. The queue with the weight value of 8 is permitted to forward 8/16 or one half of the total traffic on the associated link. The queue with the weight of 4 can forward one fourth of the traffic on the link. In such a system, if one of the queues has no traffic, then its permitted traffic is allocated among the remaining queues. For example, if the one of the queues with a weight of 2 has no traffic, then the queue with the weight of 8 can now transfer 8/14 of the total allowed link traffic.
In systems which implement one or both of these packet queuing approaches, it is possible that packets with relatively low priority will never be transferred, or will be substantially delayed, if the traffic of higher-priority packets is high. It is also possible that the amount of traffic permitted to be transferred from the queues on the link may exceed the capabilities of other lower-capacity links on the network, such as those carrying edge router data traffic.